﻿#include "doublylinkedlist.h"
#include <time.h>
#include <stdlib.h>
#include <qdebug.h>

void DoublyLinkedListNodeTest()
{
    qDebug()<<"----双向链表测试函数----";
    PNode L;
    InitList(&L);
    qDebug()<<"链表长度："<<Length(L);

    qDebug()<<"----测试头部插入----";
    CreateHead(L,10);
    qDebug()<<"链表长度："<<Length(L);
    Traverse(L);
    qDebug()<<"销毁结点个数："<<Destroty(&L);

    qDebug()<<"----测试尾部插入----";
    InitList(&L);
    CreateTail(L,20);
    qDebug()<<"链表长度："<<Length(L);
    Traverse(L);
    qDebug()<<"销毁结点个数："<<Destroty(&L);

    qDebug()<<"----测试获取第i个元素的数值----";
    InitList(&L);
    CreateHead(L,10);
    Traverse(L);

    int *data=(int*)malloc(sizeof(int));
    if(GetElem(L,6,data))
        qDebug()<<"第6个元素："<<*data;
    else
        qDebug()<<"没有找到第6个元素。";
    if(GetElem(L,2,data))
        qDebug()<<"第2个元素："<<*data;
    else
        qDebug()<<"没有找到第6个元素。";
    if(GetElem(L,8,data))
        qDebug()<<"第8个元素："<<*data;
    else
        qDebug()<<"没有找到第8个元素。";

    qDebug()<<"----测试删除第i个元素----";
    Traverse(L);
    if(Delete(L,5,data))
        qDebug()<<"第5个元素为："<<*data<<" 删除成功。";
    else
        qDebug()<<"删除第5个元素失败。";

    Traverse(L);
    if(Delete(L,11,data))
        qDebug()<<"第11个元素为："<<*data<<" 删除成功。";
    else
        qDebug()<<"删除第11个元素失败。";

    Traverse(L);
    if(Delete(L,9,data))
        qDebug()<<"第9个元素为："<<*data<<" 删除成功。";
    else
        qDebug()<<"删除第9个元素失败。";
    Traverse(L);

    qDebug()<<"----测试获取第一个和某值相等的位置----";
    Traverse(L);
    int pos=LocateElem(L,5);
    if(pos!=-1)
        qDebug()<<"值是5的结点的位置是："<<pos;
    else
        qDebug()<<"没有找到值是5的结点。";

    pos=0;
    pos=LocateElem(L,6);
    if(pos!=-1)
        qDebug()<<"值是6的结点的位置是："<<pos;
    else
        qDebug()<<"没有找到值是6的结点。";

    pos=0;
    pos=LocateElem(L,11);
    if(pos!=-1)
        qDebug()<<"值是11的结点的位置是："<<pos;
    else
        qDebug()<<"没有找到值是11的结点。";

    qDebug()<<"销毁结点个数："<<Destroty(&L);
    SAFE_DELETE(data);
    qDebug()<<"----双向链表测试函数结束----";
}

int Length(PNode L)
{
    int count=0;
    PNode p=L->next;
    while(p!=NULL){
        p=p->next;
        ++count;
    }
    return count;
}

bool InitList(PNode *L)
{
    (*L)=(PNode)malloc(sizeof(DLLNode));
    if((*L)==NULL)
        return false;
    (*L)->data=-1;
    (*L)->pre=NULL;
    (*L)->next=NULL;
}

void Traverse(PNode L)
{
    printf("Display:");
    if(L==NULL){
        printf("\n");
        fflush(stdout);
        return;
    }

    PNode p=L->next;
    while(p!=NULL){
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
    fflush(stdout);
}

void CreateHead(PNode L, int n)
{
    srand(time(NULL));
    for(int i=0;i<n;++i){
        PNode p=(PNode)malloc(sizeof(DLLNode));
        if(p==NULL)
            return;
        p->data=rand()%10;

        p->next=L->next;
        p->pre=L;

        if(L->next!=NULL)
            L->next->pre=p;

        L->next=p;
    }
}

void CreateTail(PNode L, int n)
{
    if(L==NULL)
        return;
    //p指向最后一个结点
    PNode tailNode=L;
    while(tailNode->next!=NULL)
        tailNode=tailNode->next;

    srand(time(NULL)+1);
    for(int i=0;i<n;++i){
        PNode newNode=(PNode)malloc(sizeof(DLLNode));
        if(newNode==NULL)
            return;
        newNode->data=rand()%10;
        newNode->next=NULL;
        newNode->pre=tailNode;

        tailNode->next=newNode;

        tailNode=newNode;
    }
}

int Destroty(PNode *L)
{
    int count=0;
    while((*L)!=NULL){
        PNode p=(*L);
        (*L)=(*L)->next;

        free(p);
        p=NULL;
        ++count;
    }
    return count;
}

bool GetElem(PNode L, int i, int *data)
{
    if(L==NULL)
        return false;

    PNode p=L->next;
    //记数从1开始
    int index=1;
    while(index<i && p!=NULL) {
        ++index;
        p=p->next;
    }
    if(p==NULL)
        return false;
    (*data)=p->data;
    return true;
}

int LocateElem(PNode L, int data)
{
    if(L==NULL)
        return 0;

    PNode p=L->next;
    int count=0;
    while(p!=NULL){
        ++count;
        if(p->data==data)
            return count;
        else
            p=p->next;
    }
    return -1;
}

bool Insert(PNode L, int i, int data)
{
    PNode p=L->next;
    //int index=0;
    int index=1;
    while(index<i && p!=NULL){
        p=p->next;
        ++index;
    }
    if(p==NULL)
        return false;

    PNode newNode=(PNode)malloc(sizeof(DLLNode));
    if(newNode==NULL)
        return false;
    newNode->data=data;
    newNode->next=p;
    newNode->pre=p->pre;

    p->pre->next=newNode;
    p->pre=newNode;
}

bool Delete(PNode L, int i, int *data)
{
    PNode p=L->next;
    //int index=0;
    int index=1;
    while(index<i && p!=NULL){
        p=p->next;
        ++index;
    }
    if(p==NULL)
        return false;

    (*data)=p->data;

    if(p->pre!=NULL)
        p->pre->next=p->next;
    if(p->next!=NULL)
        p->next->pre=p->pre;

    free(p);
    p=NULL;

    return true;
}
